package shuati.shua;

public class Fibonacci {
    public static void main(String[] args) {
        int n = 10; // 要计算的斐波那契数列长度
        System.out.println("斐波那契数列前 " + n + " 项为：");
        int[] memo = new int[n + 1]; // 创建数组用于保存计算结果
        for (int i = 0; i < n; i++) {
            System.out.print(fibonacci(i, memo) + " ");
        }
    }

    public static int fibonacci(int n, int[] memo) {
        if (n <= 1) {
            return n;
        } else if (memo[n] != 0) {
            return memo[n];
        } else {
            memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
            return memo[n];
        }
    }

    public static long fibonacci(int n) {
        if (n < 1) {
            return -1;
        }
        if (n ==1 || n == 2) {
            return 1;
        }

        long a = 1L, b= 1L, c = 0L;		//定义三个long类型整数
        for (int i = 0; i < n - 2; i++) {
            c = a + b;			//第3个数的值等于前两个数的和
            a = b;			//第2个数的值赋值给第1个数
            b = c;			//第3个数的值赋值给第2个数
        }
        return c;
    }
    public static long fib(int n){
        long[] arr = new long[n];
        arr[0] = arr[1] = 1;		//第一个和第二个数据特殊处理
        for (int i = 2; i < n; i++) {
            arr[i] = arr[i -2] + arr[i - 1];
        }
        return arr[n - 1];
    }
}